'''
@author:  Kevin Zhao
@Date: 16 Jan 2013
@note:exercise 12.1-3
'''
from stack import SinglyLinkedStack
from tree import binary_tree
'''
Non-recursive Tree Walker with stack
'''
def tree_walk_1(tree):
    stack = SinglyLinkedStack()
    root = tree.root
    while root!=None:
        left = root.left
        right = root.right
        if left !=None:
            stack.push(left)
        if right!=None:
            stack.push(right)
        
        print root.value
        
        root = stack.pop()
    
'''
Non-recursive Tree Walker without stack
'''
def tree_walk_2(tree):
    root = tree.root
    pre = root
    while root!=None:
        if pre.left == root:
            pre = root
            print root.value
            root = root.parent.right
            if root ==None:
                root = root.left
            if root ==None:
                root = root.right
        elif pre.parent.right == root:
            print root.value
            root = pre.left
            if root ==None:
                root = pre.right
            if root == None:
                root = root.left
            if root == None:
                root = root.right
        else:
            print root.value
            root = root.left
            if root == None:
                root = root.right
         
        
#initialization
'''
        1(root)
      /  \
    2     3
   /\    /\
  4 6   5 7
 /
8
'''
b_tree = binary_tree()
b_tree.random_insert(1)
b_tree.random_insert(2)
b_tree.random_insert(3)
b_tree.random_insert(4)
b_tree.random_insert(5)
b_tree.random_insert(6)
b_tree.random_insert(7)
b_tree.random_insert(8)

tree_walk_2(b_tree)